package cn.edu.nju.ws.sview.reasoning.schema;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;

import org.json.simple.JSONArray;
import org.json.simple.JSONObject;

import cn.edu.nju.ws.sview.cache.SubclassCache;
import cn.edu.nju.ws.sview.cache.URIIDCache;
import cn.edu.nju.ws.sview.cache.URILabelCache;
import cn.edu.nju.ws.sview.util.URIUtil;

/**
 * 对于输入的一个类的集合(可能存在层次关系，互递归)，生成这个集合传递规约后得到的树
 * @author Saisai Gong
 *
 */
public class ReducedClassTree {
	private HashSet<Integer> classes;
	public ReducedClassTree(HashSet<Integer> classes){
		this.classes = new HashSet<Integer>();
		this.classes.addAll(classes);
	}
	
    /**
     * 得到传递规约后的类层次结构
     * @return
     */
	public JSONArray getClassesJSONArray(String lang){
    	JSONArray result = new JSONArray();
    	ArrayList<ClassTreeNode> treeNodes = this.computeTransitiveReducedTree();
    	//存储了每个节点对应的json对象，首先构造完data,status,分步构造chidren
    	ArrayList<JSONObject> jsobs = new ArrayList<JSONObject>();
    	//代表顶层的json对象
    	ArrayList<JSONObject> topClassObjs = new ArrayList<JSONObject>();
    	for(int i=0 ;i<treeNodes.size();i++){
    		ClassTreeNode treeNode = treeNodes.get(i);
    		JSONObject jsob = new JSONObject();
    		jsobs.add(jsob);
    		JSONObject jsobData = new JSONObject();
    		//赋予title,attr,children会在以后中进行赋予
    		StringBuffer buffer = new StringBuffer();
    		HashSet<Integer> classes = treeNode.getClasses();
    		int count = 0;
    		int minClassID = 0;
    		for(Integer classID:classes){
    			if(minClassID==0){
    				minClassID=classID;
    			}else if(minClassID>=classID){
    				minClassID = classID;
    			}
    			count++;
    			buffer.append(classID);
    			if(count!=classes.size()){
    				buffer.append(",");
    			}
    		}
    		//title是选取强连通分支中id最小的类的title
    		String title = null;
			try {
				title = URILabelCache.getInstance().getLabel(minClassID, lang);
			} catch (Throwable e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
    		String classURI= null;
			try {
				classURI = URIIDCache.getInstance().getURI(minClassID);
			} catch (Throwable e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
    		if(title.equals("")){
    			title = URIUtil.getLocalname(classURI);
    		}
    		jsobData.put("title", title);
    		//attr里面有title, id, class_set
    		JSONObject dataAttrObj = new JSONObject();
    		//id为逆拓扑排序编号
    		dataAttrObj.put("title", classURI);
    		jsobData.put("attr", dataAttrObj);
    		jsob.put("data", jsobData);
    		
    		JSONObject thisObjAttr = new JSONObject();
    		thisObjAttr.put("id", i);
    		thisObjAttr.put("class_set", buffer.toString());
    		jsob.put("attr", thisObjAttr);
    		//判断是否是顶层类
    		ArrayList<ClassTreeNode> neighbors = treeNode.getOrderNeighbors();
    		if(neighbors.size()==0){
    			topClassObjs.add(jsob);
    		}else{
    			//当前节点是之前节点的子节点
    			for(ClassTreeNode node:neighbors){
    				int nodeID = node.getNodeID();
    				JSONObject parentObj = jsobs.get(nodeID);
    				if(parentObj.get("children")==null){
    					JSONArray children = new JSONArray();
    					parentObj.put("children", children);
    				}
    				JSONArray children  = (JSONArray)parentObj.get("children");
    				children.add(jsob);
    			}
    		}
    	}
    	for(JSONObject topObj:topClassObjs){
    		result.add(topObj);
    	}
    	return result;
    }
	
	
	/**
	 * 基于强连通分支来计算传递规约/传递闭包的新图
	 */
	public ArrayList<ClassTreeNode> computeTransitiveReducedTree(){
		//强连通分支压缩,对于压缩后的图进行逆拓扑排序，生成新的图
		ArrayList<ClassTreeNode> treeNodes =getCompressedGraph(this.classes);
		//表示传递闭包
		ArrayList<HashSet<Integer>> closure = new ArrayList<HashSet<Integer>>();
		for(int i=0;i<treeNodes.size();i++){
			closure.add(new HashSet<Integer>());
		}
		//对新的图进行传递规约/传递闭包的计算，两层循环
		//外层循环从逆拓扑序较低的节点开始来更新传递闭包
		for(int i=0;i<treeNodes.size();i++){
			ClassTreeNode treeNode = treeNodes.get(i);
			//内存循环从邻接表中逆拓扑序排序较高的节点开始更新传递闭包
			ArrayList<ClassTreeNode> neighbors = treeNode.getOrderNeighbors();
			HashSet<ClassTreeNode> toRemoved =new HashSet<ClassTreeNode>();
			for(int j=0;j<neighbors.size();j++){
				ClassTreeNode neighbor = neighbors.get(j);
				int neighborID = neighbor.getNodeID();
				HashSet<Integer> currentClosurePart = closure.get(i);
				if(currentClosurePart.contains(neighborID)){
					//意味着当前邻居可以被删除了
					toRemoved.add(neighbor);
				}else{
					currentClosurePart.add(neighborID);
					//立即将neighborID具有的闭包全部加入(已计算)
					currentClosurePart.addAll(closure.get(neighborID));
				}
			}
			//删除该删除的邻居边
		    for(ClassTreeNode removedNode :toRemoved){
		    	treeNode.deleteNeighbor(removedNode);
		    }
		}
		return treeNodes;
	}
	
	   /**
	    * 计算强连通分支压缩后的图，得到按照逆拓扑顺序排序的新图节点及其邻接矩阵
	    * @param classes
	    * @return
	    * @throws Throwable
	    */
	   private ArrayList<ClassTreeNode> getCompressedGraph(HashSet<Integer> classes){
		   ArrayList<HashSet<Integer>> orderList = new  ArrayList<HashSet<Integer>>();
		   HashMap<Integer, HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();
		   for(Integer classID:classes){
			   HashSet<Integer> superSet = new HashSet<Integer>();
			try {
				superSet = SubclassCache.getInstance().getSuperClass(classID);
			} catch (Throwable e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			   superSet.retainAll(classes) ;
			   graph.put(classID,superSet) ;
		   }
			HashMap<Integer, HashSet<Integer>> reverseGraph = new HashMap<Integer, HashSet<Integer>>();
			ArrayList<Integer> finish = new ArrayList<Integer>();
			//get the top order of classes . That is the superclass is at front
			HashSet<Integer> visited = new HashSet<Integer>();
			for(Integer shit :classes){
				if(!visited.contains(shit)){
				   Subclass.getInstance().firstDFS(shit,finish, graph,reverseGraph, visited);
				}
			}
			visited.clear();
			for (int i = finish.size() - 1; i >= 0; i--) {
				Integer classID= finish.get(i);
				if (!visited.contains(classID)){
					HashSet<Integer> set =Subclass.getInstance().secondDFS(classID, reverseGraph, visited);
					orderList.add(set) ;
				}
			}
			Collections.reverse(orderList);
			////end
			//原图节点与压缩后节点的映射
			HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
			//强连通分支压缩后的节点图
			ArrayList<ClassTreeNode> treeNodes = new ArrayList<ClassTreeNode>();
			for(int i=0;i<orderList.size();i++){
				int nodeID = i;
				HashSet<Integer> set = orderList.get(i);
				for(Integer element:set){
					map.put(element, nodeID);
				}
				ClassTreeNode treenode = new ClassTreeNode(nodeID,set);
				treeNodes.add(treenode);
			}
			
			//构造强连通分支压缩后的节点图邻接矩阵
			for(Integer element:graph.keySet()){
				HashSet<Integer> neighbors = graph.get(element);
				int nodeID = map.get(element);
				ClassTreeNode treeNode = treeNodes.get(nodeID);
				for(Integer neighbor:neighbors){
					int neighborNodeID = map.get(neighbor);
					ClassTreeNode neighborTreeNode = treeNodes.get(neighborNodeID);
					treeNode.addNeighbor(neighborTreeNode) ;
				}
			}
		    return treeNodes;
	   }
}
